package c_ch11.kruskal;

import java.util.ArrayList;
import java.util.Collections;

import c_ch11.kruskal.CC;	//UF 和 CC 在这里没有自己重新实现一遍，但都得会；
import c_ch11.Kruskal;
import c_ch11.WeightedGraph;

public class Kruskal_try {
	private ArrayList<WeightedEdge_try> ret = new ArrayList<>();
	
	public Kruskal_try(String weightedgraph) {
		WeightedGraph_try wg = new WeightedGraph_try(weightedgraph);
//		if(new CC(wg).count() != 1) return; //构造函数也是函数，可以直接return！！    //1.没有判断CC的数量，如果图不连通，就会把所有边给尝试一遍，因为达不到生成树点边关系的要求，最后会在各个CC里生成各自的生成树；
		
		ArrayList<WeightedEdge_try> edges = new ArrayList<>();
		for (int i = 0; i < wg.getV(); i++) {
			for (int edge : wg.adj(i)) {
				if(i < edge)		//2.添加边的时候应该考虑，使用顶点表示边会有重复表示的问题，不要把一条边添加两次  
					edges.add(new WeightedEdge_try(i, edge, wg.weight(i, edge)));  
			}
			
		}
		
		Collections.sort(edges);
		
		UF uf = new UF(wg.getV());      
		
		WeightedEdge_try first = edges.get(0);  		//放前两条边不会形成环
		ret.add(first);
		uf.unionElements(first.getA(), first.getB());
		
		WeightedEdge_try second = edges.get(1);
		ret.add(second);
		uf.unionElements(second.getA(), second.getB());
		
		boolean normal = false;//*
		for (int i = 2; i < edges.size(); i++) {
			//只要不形成环 一直放就行了
			WeightedEdge_try willPut = edges.get(i);
			if( uf.isConnected(willPut.getA(), willPut.getB()) )
				continue;
			
			ret.add(willPut);
			uf.unionElements(willPut.getA(), willPut.getB());  //3.这里漏掉了 debug出；这里漏了说明思路还不够清晰；
			
			if( ret.size() == wg.getV()-1 ) {  //2.没有考虑到无向边在使用顶点表示时会重复表示的问题,从而相同边占了位置 结果错误；
				normal = true;//*
				break;
			}
		}
		
		if(!normal)  //*这样写可以和Prim统一；
			ret.clear();
		
//		//**自己想到的思路，不用CC函数；
//		if(ret.size() < wg.getV()-1)  //不计环之后，边的数量怎么也达不到V-1 就说明CC>1；这也说明了用UF去环+白板顶点放边法 也可以求出CC的数量：wg.getV()-1 - size 即可
//			ret.clear();	//O(V-1) << O(ElogE)
//			//or ret = new ArrayList<>(); //或者开个白板对象 这个应该更快点 但是多消耗了点内存
	}
	
	public Iterable<WeightedEdge_try> result() {
		return ret;
	}
	
	public static void main(String[] args) {
		System.out.println( new Kruskal_try("wg.txt").result() ); 
		System.out.println( new Kruskal(new WeightedGraph("wg.txt")).result() );
	
		//可以用wg2.txt里的数据测试一下多连通分量 且 注释掉CC判断时 得到的结果：最后会在各个CC里生成各自的最小生成树；
		System.out.println( new Kruskal_try("wg2.txt").result() ); 
		System.out.println( new Kruskal(new WeightedGraph("wg2.txt")).result() );

	}
}
